#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-11-27 4:49 下午
# @Author  : yangdy
# @File    : 2020-11-27.3
# @Software: PyCharmCE
"""
某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，
我们所知道的信息只有：数组中所有整数都在 [1, k] 之间，且数组中的数字都没有前导 0 。

给你字符串 s 和整数 k 。可能会有多种不同的数组恢复结果。

按照上述程序，请你返回所有可能输出字符串 s 的数组方案数。

由于数组方案数可能会很大，请你返回它对 10^9 + 7 取余 后的结果。
"""
from tools.my_methods import *


class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        dp = [0 for i in range(len(s)+1)]
        e = 0
        for i in range(len(s)):
            e = e * 10 + ord(s[i]) - ord('0')
            if 1 <= e <= k:
                dp[i] = 1
        for i in range(len(s)):
            e = 0
            for j in range(i+1, len(s)):
                e = e * 10 + ord(s[j]) - ord('0')
                if e <= 0:
                    break
                if e <= k:
                    # dp[j] += dp[i]
                    dp[j] = (dp[j] + dp[i]) % (10**9 + 7)
                else:
                    break
        return dp[len(s)-1]

        # self.ans = 0
        #
        # def dfs(ss, ii, k):
        #     print(ss, ii, k, self.ans)
        #     if ii >= len(ss):
        #         self.ans += 1
        #         return
        #     e = 0
        #     for i in range(ii, len(ss)):
        #         if ss[i] == '0':
        #             if e == 0:
        #                 return
        #             e = e * 10 + ord(ss[i]) - ord('0')
        #         else:
        #             e = e * 10 + ord(ss[i]) - ord('0')
        #         if e > k:
        #             return
        #         dfs(ss, i+1, k)
        # dfs(s, 0, k)
        # return self.ans


questions = [
    ("1000", 10000),
    ("2553462832281151811513004352253111", 456),
    ("1000", 10),
    ("60891074110764506172567219609341401750508439262831353078571361488325177916612640603310797328738051125120717846131"
     "17784120370156131727271143390462814621391437375085466486527129089676218204148839711194278437883921052426501031253"
     "05582045204724287392517164139508054145047774846691351834197811271878504058920817228548986979423179016026199666653"
     "04800128995218492689014166497572436014469666116123834734835494959782004707983317344898415547555732791401427045917"
     "81600812772754211140474514698195019186226117392957717674651816106929133946306572613196792445763747941123774449287"
     "57043153391576113123048655449597251789349981237533002529307052190839941664218022700212215482148674443541706406557"
     "78060881185312113449809395839371233617661145065455143835813142890713447090432568664680208516212709578099031091759"
     "01167078865133742037111359587159241998105780304164381743145775241091221621579844351889974043643863315674778916416"
     "33291850892781082353411264531879596582132092315280827185411678040326478146178091166059625171944551014678921657736"
     "78155599513111463856101333503294122559232092158131623814902871169003197185160930924057148652078117299530155116038"
     "15591845934119787685396806685844414542666167978410169047996165729716348094557747203113439318178776996161154713103"
     "55388019146344491955423562334915972782811390256344726486171992387312650771649664041162438771145314461410879831742"
     "17204189485699885596901778841272952396320001088106578451111400745158928430155568653104453358915879838908816116031"
     "09486744753713190395818624492719377654569356381122536579291759031124845101149628915838053316640033228150020811065"
     "96958416415822448433051383100686968184592219114060198832149113134633117100764117651553314706146271045419114758632"
     "37003363407539029166104121544651748977051406813341031344461927709196096079846618670176697581317948814498739411256"
     "61462626156757260684116632875144280856591365821756627087022789146755553750294202142103213068105545165188101785585"
     "18527310413838700012780371530291912177601341691035091836451741117299303503817710519666914549808015735553818240024"
     "51030243591706405295534556818809249730400229191886532637661971649280286841974712439461817452379355346741676800523"
     "93952813231244119190145814008339125561939179737536740165291195418981486778359067479544846152150889277275888161659"
     "66073127482939182160001192664029152624835176467870189846895516883728221361401126484087879839724963840785728891871"
     "75724042179458992120344927145813189607212591972527524228344189236464144153107134824979477561831805394425137971294"
     "90453318163670579395578296912703825697571300118126988055344889781377788571674874261435267873212447838732360141602"
     "91471039872148697792108065566157825109411642102154975597419052631438018471855246603719180671336162528231388341417"
     "65218826303502915028213889777101461560213552369818125899641765422196185461921538232607147317465741051867326196012"
     "09150415019927790053104230172625514978267778348866178379671847584291064758901456793591312696001151987671232753751"
     "68909128812627791911116001932258619119820095014771556166881577244841576792365837753411518753561362398142466918137"
     "80290723836480213721681771013561403897977694558917892772218842372518674456823675547145324312164845204181932686411"
     "808461740292028523889212102901111929606155338855232046126855218432978314774361915960914343696543599694371232881619845676516651444679470621609217192247971627686121079398623245392744249059381236516657455312673526520302691144721851522625181329219216042298032976975974797869701278514761530611642199878928355108090379102610204659076168161159919021084914486123012781628318002182729861670124405342368650496477291171751120726175001622480182268938986413631190317184970578812046567212403838379591059969170991127540511060927781479871141509267847936608487338364133300360186308262490886754417692914270618950318179856774829862271338945361652458595065037715692016011614438914867476210140708759873546160522644090737116519501299952571182786125604342163105157633133179883254874252412865981407740447341277707171369408152432688129616324483921754108487615536577269029375277385237858541745509216113632317786302089514306115840719627972861055586191775567088897035918670466017603995688262787155845976209005501837455237117387552942512018413127199992119339463503592451099663171809379781877021791537400981897914121244104151519547746921910082856717700488768901462719928272844071401557623293530398171886658776655685296153413273678882845691917295834986012387834571107232191693935631685213101740725271737077501563736291876334922462570190733846230188295027360181581886177660315110934362713319781131443433163880312021794348860676105632276116197609105464637177859918122022621131051118452726703167091116651021540073446651172250582081492446411649146302120049973922698102062145122096184134813693116829407421824514590229553827363817427119128608525473137189855662193390229206520975038963634804217333349525819614204301067397800712849339614670596212413375184270109379070941786259541572882445321942617633050012086119158794883107349728134955809112924331104240914198810712428306715854609716261349216361987327672322774950013768504370524257108398086326992321495167981852096781028716984719240217016607965493721164807445641485892657235139108365935963396568109914712513662824083483818116531439420120349569436815731050250723372161496042830614841031643362045421161425245168121565113983871238405401497207121391080281099298771713768111723897142038063590197627172714291673023971321575758381004818740057384474125155574956170041331287820058795674745603037151752464118210611790342441013698411842632147096463434524681043623993500271354095926457891927176058392773812015166598606076112523150522057741158376441470265512518766518691276188519362426066081744579695188442811210305410905531750321464585879851104823351716008591571857485051174317195630597387204638058016823587923989740369983981304553131319384848608739497430583150532927613484211860495413402939716481630413744423211854265078101478133329830172719197186527825068783211539706711755665963853894246214819574909155073718187160352159759911135564031075010758725686141510229234447428216215114116555268439119115709959827221285286597213989739191225561126126663382426421060542959837048215937940447374148788943641636423103870459084759179503509782244125418530219673667386158597316172936825153406855119897871779799406122849926702830678946165849218305345731108743151277365985063552319230888263987273765899109963580613789529214262943971905631866034429307537433855010776496431578178289080097416036549122044371148861111457113399242360589686481329017178968867918773830719936274508220204267794150948162193135677136058799689513577447189045355074750549858078477792923341173985466160787167157003975159678234190916316152748612150409384848632451485322441696368719171021714454458418290886332712884245708616380910139856773896253178269319240021208900010118198519839261877680932133838685978567221862270264009670234101722168170411124862011525915963012214114347965862581084103802182232280171922895651912225847050733917062947664527286153827165414729674447096536903920130207943509694472466104518301265224706452573124771373463623385377789171970860085512806135317863118315168505949468271854593591211797171765252805949927168878960147033626344391221586087301283810091822062504824355015539106514004833316763845313682993016821465236937128772417914292814674976251267797953139912298854811012317310248378182092769811552331583975156152823816262516616757172297474018156752088102782576148795278108269384675513991825277561777262567554673326553941751857371866989752688189363185025540442315958430018161947854521154535618871992503614159002917972706017140050155442659179862722192543621775748476331707516194554142354653185319832961537331929623472154095818483150012345909388758803287034545891845617884017471676958949945523448647176506585821449531322785362167902852239141181175094108251295183211565153565050145470316696533810750261711541868497665368143932142310161234955610114219128554641625863108661020122121845170251873167253968409151309536098866710626003636265141163313148307804216630149554199383360741346553337104088286184605595113118309116909793296330601357251094341329120311097713034010774661286572037178064234102740616295464117394550183428940108447598541883515975714713265505617840947619377031615750973710918002815115588019335765646336634744954168331858980953801704655495079935784943771031817152938434877162677716140751588016218488963016639528465654335154812125471570561683125711269307521128969821291395581249167621924393511465088712686454185271669738057943863512",
     194014911),
]

work(questions, lambda q: Solution().numberOfArrays(q[0], q[1]))

